package com.lwt.codetop.linkedLists;

// 141. 环形链表

/**
 * 链表判断是否存在环
 * 思路：快慢指针，相遇则表明存在环
 */
public class LinkedListCycle {
    public static void main(String[] args) {
        //构建测试用例 创建有环链表
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        // 制造环，让 node4 的 next 指向 node2
        head.next.next.next.next = head.next;

        // 判断链表是否存在环
        boolean res = hasCycle(head);
        System.out.println(res);
    }

    private static boolean hasCycle(ListNode head) {
        if(head == null) return false;
        // 快慢指针，快走二，慢走一，相遇则表明存在环
        ListNode fast = head, slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
        return false;
    }
}
